import java.util.Arrays;

public class Test {
//分治法
    //时间复杂度为0（Nlongn）
    //树的高度为longn  但每个结点都要查一下
    public static void quickSort(int[] array,int left,int right){ //相信这个函数一定帮我们完成排序数组

        //然后的想出口了
        //
        if(left>=right){   //为啥还有大于了，想一个情况当为有序的，你从右边往回找比基准小的，没找到，此时当返回的是基准的下标
                             //然后下面不是还要递归调用quickSort，由于里面有个参数为datum-1，此时left比datum-1大，所以这种
                           //情况也得返回
            return;
        }
        //1.找基准
        int datum = FindDatum(array,left,right);

        //2.把基准左边的数组排成有序，就相信这个函数一定能完成（黑盒）
        quickSort(array,left,datum-1);

        //3.把基准右边的数组排成有序
        quickSort(array,datum+1,right);


    }

    public static int FindDatum(int[] array,int left,int right){

               //寻找基准方法
        //第一步我们先假设第一个元素是我们的基准值，然后把比它大的数放到它的右边，比它小的数放到它的左边即可
        //那么如何实现呢，通过从右往左找到比基准值小的的跟array[left]交换，
        //那就有个问题为啥不能从左往右呢？这种情况是不可以的，有风险，因为我们开始的设的基准值是第一个，
        //如果第一个元素就比array[right]大，那么经过交换后，我们最后一个元素就不在了，
       int datum=array[left];
        while(left<right){
            while(left<right&&array[right]>=datum){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=datum){
                left++;
            }
            array[right]=array[left];
        }
        //最后left和right相遇了然后把基准值赋给相遇的这个下标即可
        array[left]=datum;
        return left;

    }
    public static void main(String[] args) {

               int[] array=new int[]{6,7,3,9,6,1};
               quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}
